package com.code.test.dance;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 * <p>
 * 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 * <p>
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * <p>
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * <p>
 * 注意：
 * <p>
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于 maxWidth。
 * 输入单词数组 words 至少包含一个单词。
 * 示例 1:
 */
public class FullJustify {

    public static void main(String[] args) {

        String[] words = {"What", "must", "be", "acknowledgment", "shall", "be"};

        List<String> ret = fullJustifyGreedy(words, 16);
        for (String item : ret) {
            System.out.println(item);
        }
    }

    /**
     * https://github.com/javasmall/bigsai-algorithm/blob/master/leetcode/problems/LeetCode%2068%E6%96%87%E6%9C%AC%E5%B7%A6%E5%8F%B3%E5%AF%B9%E9%BD%90.md
     */
    public static List<String> fullJustify(String[] words, int maxWidth) {
        List<String> vaList = new ArrayList<String>();
        List<String> teamList = new ArrayList<String>();
        int strlen = 0;
        for (int i = 0; i < words.length; i++) {
            String str = words[i];
            //当前行单词长度 + 下一个单词长度（words[i]） + 单词行数量-最少空格数量
            if (strlen + str.length() + teamList.size() <= maxWidth) {
                teamList.add(str);
            } else {
                String team = addstr(teamList, words, maxWidth, strlen, false);
                vaList.add(team);
                teamList.clear();
                teamList.add(str);
                strlen = 0;
            }
            strlen += str.length();
        }
        String team = addstr(teamList, words, maxWidth, strlen, true);
        vaList.add(team);
        return vaList;

    }

    private static String addstr(List<String> teamList, String words[], int maxWidth, int strlen, boolean isLast) {
        //组合成一个字符串返回
        //System.out.println(teamList.toString());
        StringBuilder sb = new StringBuilder();
        if (isLast) {
            for (String str : teamList) {
                sb.append(str);
                sb.append(' ');
            }
            if (sb.length() > maxWidth) {
                return sb.deleteCharAt(maxWidth).toString();
            }
            for (int i = sb.length(); i < maxWidth; i++) {
                sb.append(' ');
            }
        } else {
            //计算空格总数量
            int spaceNum = maxWidth - strlen;
            int aveNum;
            if (teamList.size() == 1) {
                aveNum = 1;
            } else {
                //计算每个单词后需要多少空格
                aveNum = spaceNum / (teamList.size() - 1);
            }

            //还剩多少空格需要填充
            int more = spaceNum - aveNum * (teamList.size() - 1);//不能平均分 多出来的空格

            sb.append(teamList.get(0));
            for (int i = 1; i < teamList.size(); i++) {
                int spaceAdd = aveNum;
                if (more-- > 0) {
                    spaceAdd++;
                }

                for (int j = 0; j < spaceAdd; j++) {
                    sb.append(' ');
                }
                sb.append(teamList.get(i));
            }
            for (int i = sb.length(); i < maxWidth; i++) {
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    /**
     * 解法：贪心算法
     * https://blog.csdn.net/lvhao123456789/article/details/138574915
     * <p>
     * 思路就是按照上面的规则来个每一行放置单词。
     * <p>
     * 我们可以总结出以下几种情况。
     * <p>
     * 除最后一行外，每一行的单词有两种情况。
     * 当该行单词数 > 1时，需要给单词之间加空格，最后一个单词刚好放到末尾，后面无空格。
     * 当该行单词数 = 1时，只需要给该单词后面加空格。
     * 如果是最后一行，除最后一个单词外，需要给每个单词后面加一个空格。最后一个单词后面补充剩余的空格。
     * 总结出以上情况后，那我们就可以构建思路了。
     * <p>
     * 我们可以记录几个变量curWidth代表当前行的单词长度，curNums代表当前行的单词个数，words[i]代表下一个要添加的单词。当curWidth + words[i].length() + curNums <= maxWidth时，当前行就可以加入新单词；否则，将当前行组成的字符串加入结果集。curWidth和curNums重置为0。
     * <p>
     * 接下来就是怎么添加单词后面的空格了。我们可以计算当前行可以添加的空格数量，然后根据上面总结的情况将空格合理分配到单词后面。这块可以看代码实现，我已将部分重要的注释加入到代码中。
     */
    public static List<String> fullJustifyGreedy(String[] words, int maxWidth) {
        List<String> list = new ArrayList<>();
        int i = 0;
        // 记录当前行的单词长度
        int curWidth = 0;
        // 记录当前行的单词个数
        int curNums = 0;
        List<String> team = new ArrayList<>();
        while (i < words.length) {
            // 当前行单词长度 + 下一个单词长度 + 当前行的单词数量（最少空格数量） < 最大宽度，说明可以把下一个单词加入当前行
            if (curWidth + words[i].length() + curNums <= maxWidth) {
                //计算每一行
                curWidth += words[i].length();
                curNums++;
                team.add(words[i]);
                i++;
            } else {
                // 空格个数
                int spaces = maxWidth - curWidth;
                int a = 0;
                int b = 0;
                // 当前行单词数 > 1 时
                if (curNums - 1 != 0) {
                    // 除当前行的最后一个单词外，每个单词后面至少加a个空格，前b个单词后面还需要再加1个空格
                    /**
                     * 平均计算每个单词后面需要多少个空格
                     */
                    a = spaces / (curNums - 1);
                    /**
                     *  计算单词后面还需要多少个空格
                     */
                    b = spaces % (curNums - 1);
                }
                StringBuilder lineBuilder = new StringBuilder();
                //目的是让左右两边都有单词，中间用空格填充
                for (int j = 0; j < team.size() - 1; j++) {
                    // 加单词
                    lineBuilder.append(team.get(j));
                    // 加空格，每个单词后需要均匀加多少空格
                    for (int k = 0; k < a; k++) {
                        lineBuilder.append(' ');
                    }
                    //所有单词后还需要加多少空格
                    if (b-- > 0) {
                        lineBuilder.append(' ');
                    }
                }
                // 加当前行的最后一个单词，最后用一个单词兜底
                lineBuilder.append(team.get(team.size() - 1));
                // 如果该行只有一个单词，需要在单词后面的剩余空间加上空格
                if (curNums == 1) {
                    while (spaces-- > 0) {
                        lineBuilder.append(' ');
                    }
                }
                // 当前行加入结果集
                list.add(lineBuilder.toString());
                // 当前行加入结果集后，当前行宽度和当前行单词个数重置为0
                curWidth = 0;
                curNums = 0;
                team.clear();
            }
        }

        /**
         * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
         * 每个单词之间只有1个空格，最后把所有空格补充在最后，目的是为了形成左对齐
         */
        //处理上面遗留的最后一行
        StringBuilder lineBuilder = new StringBuilder();
        // 最后一行结果集先加单词，再加1个空格
        for (int j = 0; j < team.size() - 1; j++) {
            lineBuilder.append(team.get(j));
            lineBuilder.append(' ');
        }
        // 剩余空格个数
        int spaces = maxWidth - curWidth - (curNums - 1);
        lineBuilder.append(team.get(team.size() - 1));
        // 最后一个单词后面把剩余空格都加上
        while (spaces-- > 0) {
            lineBuilder.append(' ');
        }
        // 最后一行加入结果集
        list.add(lineBuilder.toString());
        return list;
    }
}
